package leetcode_1000;

import java.util.HashSet;
import java.util.Set;

/**
 *@author 周杨
 *MinimumIncrementToMakeArrayUnique_945_ 一个数组元素只能一次+1 问给定数组变成不重复元素的数组最短需要多少这种操作
 *describe:用预留位标记重复元素 AC
 *2018年11月25日 下午4:05:25
 */
public class MinimumIncrementToMakeArrayUnique_945_ {
	
	/**
	 * describe:计算重复的个数
	 * 2018年11月25日 下午4:04:30
	 */
	public int minIncrementForUnique(int[] A) {
		int[] count = new int[100000];
        for (int x: A) count[x]++;

        int ans = 0, taken = 0;//token表示前面的预留位置 就是重复了多少
        for (int x = 0; x < 100000; ++x) {
            if (count[x] >= 2) {
                taken += count[x] - 1;
                ans -= x * (count[x] - 1);//先减去这么多数字
            }
            else if (taken > 0 && count[x] == 0) {
                taken--;
                ans += x;//因为之前减过了该数字 那么现在加上的就是要补的差值
            }
        }

        return ans;
    }
	
	/**
	 * describe:超时
	 * 2018年11月25日 下午2:48:17
	 */
	public int minIncrementForUnique1(int[] A) {
        Set<Integer> set=new HashSet<Integer>();
        int res=0;
        for(int i:A) {
        	while(set.contains(i)) {
        		++res;
        		i++;
        	}
        	set.add(i);
        }
        return res;
    }
}
